#include "leetcode_util.h"

// Function to find length of longest increasing subsequence
int helper1(vector<int>& A, int i, int n, int prev)
{
	// Base case: nothing is remaining
	if (i == n)
		return 0;

	// case 1: exclude the current element and process the
	// remaining elements
	int excl = helper1(A, i + 1, n, prev);

	// case 2: include the current element if it is greater
	// than previous element in LIS
	int incl = 0;
	if (A[i] > prev)
		incl = 1 + helper1(A, i + 1, n, A[i]);

	// return maximum of above two choices
	return max(incl, excl);
}
int solution1(vector<int>& A) {
    return helper1(A, 0, A.size(), INT_MIN);
}

// Iterative function to find length of longest increasing subsequence
// of given array
int solution2(vector<int>& A)
{
	// array to store sub-problem solution. L[i] stores the length
	// of the longest increasing subsequence ends with arr[i]
    int n = A.size();
	vector<int> dp(n, 0);

	// longest increasing subsequence ending with arr[0] has length 1
	dp[0] = 1;

	// start from second element in the array
	for (int i = 1; i < n; i++)
	{
		// do for each element in subarray arr[0..i-1]
		for (int j = 0; j < i; j++)
		{
			// find longest increasing subsequence that ends with arr[j]
			// where arr[j] is less than the current element arr[i]

			if (A[j] < A[i] && dp[j] > dp[i])
				dp[i] = dp[j];
		}

		// include arr[i] in solution2
		dp[i]++;
	}

	// find longest increasing subsequence (having maximum length)
    return *max_element(dp.begin(), dp.end());
}
/*
# 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
# 0, 4, 6, 9, 11, 15 or
# 0, 4, 6, 9, 13, 15
def LongestIncreasingSubsequence(A):
    l = len(A)
    dp = [ 1 for x in range(l) ]
    for i in range(1, l):
        for j in range(i):
            if A[i] >= A[j] and dp[i] <= dp[j]:
                dp[i] += 1
    return max(dp)

print(LongestIncreasingSubsequence([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
*/

void showVector(vector<int>& A) {
    vector<int>::iterator itr = A.begin();
    for(; itr != A.end();) {
        printf("%d", *itr);
        if (++itr != A.end()) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
}

void testVector(int argc, char *argv[]) {
    string s;
    for (int i = 1; i < argc; i++) {
        s = string(argv[i]);
        vector<int> v = stringToVector(s);
        // test function

        // cout << numberOfArithmeticSlices(v) << endl;
    }
}

int main(int argc, char *argv[]) {
    string s("[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]");
    //string s("[0, 8, 2, 4, 10, 6, 7]");
    vector<int> a = stringToVector(s);
    cout << s << endl;
    
    int result;
    int N = 10000;
    clock_t c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution1(a);
    }
    cout << "solution1: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution2(a);
    }
    cout << "solution2: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
/*
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution3(a, b);
    }
    cout << "solution3: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
*/
}

